To achieve efficient sorting, we must analyze three key dimensions that govern an algorithm's performance. Effective design often involves finding the optimal trade-off among these metrics.
- Time Complexity (Efficiency):
- Measures how an algorithm's execution time scales with input size $n$.
- Described using Big O notation. We prefer lower growth rates, e.g., $O(n \log n)$ is much better than $O(n^2)$ for large inputs.
- Space Complexity (Memory):
- Quantifies the auxiliary space required, excluding the input array itself.
- Classified as in-place (requiring $O(1)$ extra space) or out-of-place (requiring $O(n)$ extra space).
- Stability & Other Constraints:
- Stability ensures that elements with equal values maintain their original relative order after sorting.
- Other factors include cache performance, parallelizability, and handling data larger than memory.
Summary of Key Dimensions
| Dimension | What It Measures | Notation/Classification |
|---|---|---|
| Time Complexity | Scaling of computation steps with input size $n$. | $O(n^2)$, $O(n \log n)$ |
| Space Complexity | Auxiliary memory usage (excluding input $A$). | In-Place ($O(1)$) or Out-of-Place ($O(n)$) |
| Stability | Preservation of relative order of equal elements. | Stable or Unstable |